package MysingleList;

import java.util.Stack;

public class MysingleList {
	static class ListNode {
		public int val;
		public ListNode next;
		public ListNode(int val) {
			this.val=val;
		}
	}
	public ListNode head;
	public void createList() {
		ListNode node1=new ListNode(12);
		ListNode node2=new ListNode(23);
		ListNode node3=new ListNode(34);
		ListNode node4=new ListNode(56);
		ListNode node5=new ListNode(78);
		ListNode node6=new ListNode(89);

		node1.next=node2;
		node2.next=node3;
		node3.next=node4;
		node4.next=node5;
		node5.next=node6;

		this.head=node1;
	}
	public void display() {
		ListNode cur=head;
		while(cur!=null) {
			System.out.print(cur.val+ " ");
			cur=cur.next;
		}
		System.out.println();
	}

	public int size() {
		int cnt=0;
		ListNode cur=head;
		while(cur!=null) {
			cnt++;
			cur=cur.next;
		}
		return cnt;
	}
	public boolean contains(int key ) {
		return false;
	}

	//头插法
	public void addFirst(int data ) {
		ListNode node=new ListNode(data);
		node.next=head;
		head=node;
	}

	public void addLast(int data) {
		ListNode cur=head;
		ListNode node=new ListNode(data);
		//还要判断特殊情况
		if(head==null) {
			head=node;
			return;
			//当头指针是空的时候，程序跑到这就应该直接结束的
		}
		while(cur.next!=null) {
			cur=cur.next;
		}
		cur.next=node;
	}

	//任意位置插入，第一个数据节点的下标是0
	//例如第二个位置走一步即可
	public void addIndex(int index,int data) {
		if(index<0||index>size()) {
			throw  new IndexOutofException( index+ "位置不合法");
		}
		ListNode node=new ListNode(data);
		if(index==0) {
			addFirst(data);
			return ;
		}
		if(index==size()) {
			addLast(data);
			return ;
		}
		//当程序走到这里的时候就已经不可能发生空指针的异常的情况
		ListNode cur=findIndexSubOne(index);
		node.next=cur.next;
		cur.next=node;
	}
	private ListNode findIndexSubOne(int index) {
		ListNode cur=head;
		while(index-1!=0) {
			cur=cur.next;
			index--;
		}
		return cur;
	}

	//删除第一次出现关键字为key的节点
	public  void remove(int key) {
		if(head==null) {
			return ;
		}
		//删除涉及头删除和尾删除
		if(head.val==key) {
			head=head.next;
			return;
		}
//		ListNode cur=head.next;
//		ListNode prev=head;
//		while(cur!=null) {
//			if(cur.val==key) {
//				prev.next=cur.next;
//			}
//			prev=prev.next;
//			cur=cur.next;
//		}
		ListNode cur=searchPrev(key);
		if(cur==null) {
			System.out.println("没有要删除的数据");
			return;
		}
		ListNode del=cur.next;
		cur.next=del.next;
	}
	//这个是用来找到要删除的前驱，并返回
	private ListNode searchPrev(int key ) {
		ListNode cur=head;
		while(cur.next!=null) {
			if(cur.next.val==key) {
				return cur;
			}
			cur=cur.next;
		}
		return null;
	}
	//双指针删除重复的数据
	public  void removeAllKey(int key) {
		if(head==null) {
			return ;
		}
		//我们后面是拿cur进行判断的，这一步是防止prev所指的是也是要删除的
		ListNode cur=head.next;
		ListNode prev=head;
		while(cur!=null) {
			if(cur.val==key) {
				prev.next=cur.next;
			} else {
				prev.next=cur;
				prev=cur;
			}
			cur=cur.next;
		}
		if(head.val==key) {
			head=head.next;
		}

	}
	public void clear() {
		this.head=null;
	}
	//进行创建环，来进行检验
	public void createLoop() {
		ListNode cur=head;
		while(cur.next!=null) {
			cur=cur.next;
		}
		cur.next=head.next;
 	}
	public ListNode detectCycle() {
		if(head==null) {
			return null;
		}
		ListNode fast=head;
		ListNode slow=head;
		while(fast!=null&&fast.next!=null) {
			fast=fast.next.next;
			slow=slow.next;
			if(fast==slow) {
				break;
			}
		}
		//fast.next==null是为了防止只有一个节点
		if(fast==null||fast.next==null) {
			return null;
		}
		slow=head;
		while(fast!=slow) {
			fast=fast.next;
			slow=slow.next;
		}
		return fast;
	}
	public boolean hasCycle() {
		//有没有环，看快慢指针是否能够相遇
		//这里最好一个走一步，一个走两步，如果一个走的步数较多，会进行跳过另一个
		ListNode fast=head;
		ListNode slow =head;
		while(fast!=null&&fast.next!=null) {
			fast=fast.next.next;
			slow=slow.next;
			if(fast==slow) {
				return true;
			}
		}
		return false;
	}
	//利用栈来进行逆序打印链表
	public void reverPrintList() {
		Stack<ListNode> stack=new Stack<>();
		ListNode cur=head;
		while(cur!=null) {
			stack.push(cur);
			cur=cur.next;
		}
		while(!stack.isEmpty()) {
			ListNode top=stack.pop();
			System.out.print(top.val+ " ");
		}
		System.out.println();
	}
}
